import sortedcontainers


class Solution(object):
    def maxTaxiEarnings(self, n, rides):
        rides.sort(key=lambda x: x[1])
        print(rides)
        ans = sortedcontainers.SortedDict()
        for s, e, t in rides:
            t = t + e - s
            last_index = ans.bisect_right(s)
            if last_index == 0:
                now_val = t
            else:
                now_val = t + ans.peekitem(last_index - 1)[1]
            insert_index = ans.bisect_right(e)
            if insert_index == 0:
                ans[e] = now_val
            else:
                r_key, r_val = ans.peekitem(insert_index - 1)
                if e == r_key:
                    ans[e] = max(ans[e], now_val)
                else:
                    if now_val > r_val:
                        ans[e] = now_val
        return max(ans.values())


data = Solution()
n = 10
rides = [[9, 10, 2], [4, 5, 6], [6, 8, 1], [1, 5, 5], [4, 9, 5], [1, 6, 5], [4, 8, 3], [4, 7, 10], [1, 9, 8], [2, 3, 5]]
print(data.maxTaxiEarnings(n, rides))